package com.jojo.elementary.day13_tree;

import com.jojo.elementary.entity.TreeNode;

/**
 * 700、二叉搜索树中的搜索
 *
 * 给定二叉搜索树（BST）的根节点root和一个整数值val。
 * 你需要在 BST中找到节点值等于val的节点。 返回以该节点为根的子树。 如果节点不存在，则返回null。
 *
 * 示例 1:
 * 输入：root = [4,2,7,1,3], val = 2
 * 输出：[2,1,3]
 *
 * 示例 2:
 * 输入：root = [4,2,7,1,3], val = 5
 * 输出：[]
 *
 */
public class SearchTree {

    /** myCode 迭代 */
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null){
            if (root.val == val){
                return root;
            }else if(root.val < val){
                root = root.right;
            }else{
                root = root.left;
            }
        }
        return null;
    }

    /** pe.递归 */
    public TreeNode searchBST2(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (val == root.val) {
            return root;
        }
        return searchBST(val < root.val ? root.left : root.right, val);
    }
}
